package com.qying.sort;

import java.util.Arrays;

public class CountingSort {

    public static void main(String[] args) {
        int[] arr = Number.arr;

        for (int i : arr) {
            System.out.print(i + ",");
        }
        System.out.println();

        arr = countingSort(arr);

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    private static int[] countingSort(int[] arr) {

        if (arr.length == 0) return arr;

        int bias,min = arr[0],max = arr[0];

        for (int i = 1; i < arr.length;i++){
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i]< min) {
                min = arr[i];
            }
        }

        bias = 0-min;

        int[] bucket = new int[max -min +1];
        Arrays.fill(bucket,0);

        for (int i = 0; i< arr.length; i++) {
            bucket[arr[i] + bias] ++;
        }

        int index = 0,i=0;

        while (index < arr.length) {
            if (bucket[i] != 0) {
                arr[index] = i -bias;
                bucket[i]--;
                index++;
            }else {
                i++;
            }
        }

        return arr;
    }
}
